package tree;


import java.util.Scanner;
import java.util.Stack;

/**
 * @author Liangyaoyun
 */
public class BinaryTree {
    private static class Node {

        String data;  //数据域
        Node lChild;  //左孩子
        Node rChild;  //右孩子

        public Node(String data) {
            this.data = data;
        }

    }

    /**
     * 通过输入二叉树节点内容的方式构建二叉树
     * 二叉树节点内容以字符数组形式进行保存
     * 数组中的字符'#'表示空节点
     * @return 二叉树的根节点
     */
    public Node buildBinaryTreeByArray() {

        System.out.println("请输入二叉树节点内容：");

        Scanner s = new Scanner(System.in);
        String content = s.next();

        char[] contentArray = content.toCharArray();

        //1.第1轮循环：将contentArray中保存的节点内容转换为二叉树节点
        Node[] nodes = new Node[contentArray.length];

        for(int i = 0; i < contentArray.length; i++) {
            if(contentArray[i] != '#') {
                nodes[i] = new Node(contentArray[i] + "");
            }
        }

        //2.第2轮循环：根据完全二叉树节点在数组之间的下标关系，构建左右孩子指针域的引用关系
        for(int i = 0; i < nodes.length; i++) {
            if(nodes[i] != null) {
                int leftIndex = 2*i+1;  //左孩子节点下标
                int rightIndex = 2*i+2;  //右孩子节点下标

                //挂载左孩子
                if(leftIndex < nodes.length && nodes[leftIndex] != null) {
                    nodes[i].lChild = nodes[leftIndex];
                }

                //挂载右孩子
                if(rightIndex < nodes.length && nodes[rightIndex] != null) {
                    nodes[i].rChild = nodes[rightIndex];
                }

            }
        }

        //数组中下标为0的节点就是整棵树的数根节点
        return nodes[0];

    }

    /**
     二叉树的深度优先遍历
     先序遍历
     栈结构实现
     root为树根节点
     */
    public void preorderTraversalStack(Node root) {

        //防止空树的情况
        if(root == null) {
            return;
        }

        //创建先序遍历使用的栈结构
        Stack<Node> stack = new Stack<>();

        //首先将整棵二叉树的根节点入栈
        stack.push(root);

        //循环条件为栈结构非空
        while(!stack.isEmpty()) {

            //（子）树根节点出栈并遍历
            Node node = stack.pop();
            System.out.print(node.data + ", ");

            /*
             左右孩子节点逆向入栈
             保证出栈及遍历顺序为先左后右
             */

            //右孩子（右子树根）节点入栈
            if(node.rChild != null) {
                stack.push(node.rChild);
            }

            //左孩子（左子树根）节点入栈
            if(node.lChild != null) {
                stack.push(node.lChild);
            }

        }

    }

    /**
     二叉树的深度优先遍历
     中序遍历
     栈结构实现
     root为树根节点
     */
    public void inorderTraversalStack(Node root) {

        if (root == null) {
            return;
        }

        Stack<Node> stack = new Stack<>();

        Node node = root;
        while (node != null || !stack.isEmpty()) {

            while (node != null) {
                stack.push(node);
                node = node.lChild;
            }

            node = stack.pop();
            System.out.print(node.data + ", ");

            node = node.rChild;
        }

    }

    /**
     二叉树的深度优先遍历
     后序遍历
     栈结构实现
     root为树根节点
     */
    public void postorderTraversalStack(Node root) {

        //防止空树的情况
        if (root == null) {
            return;
        }

        //创建后序遍历使用的栈结构
        Stack<Node> stack = new Stack<>();

        /*
         通过节点类型变量node
         维护某一节点与其左孩子之间
         加入栈结构的相对顺序
         */
        Node node = root;

        //上次访问的结点
        Node lastVisitNode = null;
        while (node != null || !stack.isEmpty()) {

            /*
             保证对于任意节点来说
             它与它的左孩子相邻入栈
             并且以左孩子->根节点的顺序出栈
             */
            while (node != null) {
                stack.push(node);
                node = node.lChild;
            }

            //查看栈顶元素，但是并不弹出
            node = stack.peek();
            if (node.rChild == null || node.rChild == lastVisitNode) {

                /*
                 若此时栈顶节点右子树为空
                 或右子树已经被访问
                 则出栈并处理栈顶结点
                 */
                node = stack.pop();
                System.out.print(node.data + ", ");

                /*
                 在下一次循环中
                 当前被处理节点将成为
                 上一次处理过的节点
                 */
                lastVisitNode = node;

                //node变量置为null，避免死循环
                node = null;
            } else {
                //否则处理右子树
                node = node.rChild;
            }
        }

    }

    public int getHigh(Node root) {

        if(root == null) {
            return 0;
        }

        int lHigh = getHigh(root.lChild);

        int rHigh = getHigh(root.rChild);

        return Math.max(lHigh, rHigh) + 1;

    }

    public static void main(String[] args) {

        BinaryTree bt = new BinaryTree();

        //ABCDEFGH##I#JK#
        BinaryTree.Node root = bt.buildBinaryTreeByArray();

        System.out.print("树的高度: ");
        System.out.println(bt.getHigh(root));
        System.out.print("先序遍历: ");
        bt.preorderTraversalStack(root);
        System.out.print("中序遍历");
        bt.inorderTraversalStack(root);
        System.out.print("后序遍历");
        bt.postorderTraversalStack(root);
    }
}
